package airthmetic.exercise.dp;

public class _115_不同的子序列 {


    public int numDistinct(String s, String t) {
        /**
         因为问题具备重叠子问题和无后效性及最优子结构。 动态规划！
         什么是原问题？什么是子问题？
         原问题：字符串s的子序列中字符串t出现的次数
         子问题：字符串s-1的子序列中字符串t-1出现的次数

         1.确定状态参数和选择
         状态参数：字符串s的前i个字符 与字符串t的前j个字符为状态参数
         选择/决策： 不断选择i,j

         2.定义dp table的含义
         int[][] dp = new int[m+1][n+1];
         dp[m][n]表示 前m个字符的s的子序列中 前n个字符的t的出现个数


         3.初始化dp talbe
         当s是空串t也是空串的时候，也算包含一次
         当s不为空串t为空串时，也算包含一次
         当t不为空串s为空串时，不包含

         for(int i=0; i<=m; i++){
         dp[i][0] = 1;
         }

         4.推导状态转移公式
         由子问题推导原问题的解

         // i == j 有两种情况 选择当前和不选择当前
         if(ss[i-1] == tt[j-1]){
         dp[i][j] = dp[i-1][j] + dp[i][j];
         }else{
         dp[i][j] = dp[i-1][j];
         }
         */

        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        int m = ss.length;
        int n = tt.length;
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <=m; i++) {
            for (int j = 1; j <=n; j++) {
                if (ss[i - 1] == tt[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i-1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[m][n];

    }


    // 状态压缩
    public int numDistinct2(String s, String t) {
        /**
         因为问题具备重叠子问题和无后效性及最优子结构。 动态规划！
         什么是原问题？什么是子问题？
         原问题：字符串s的子序列中字符串t出现的次数
         子问题：字符串s-1的子序列中字符串t-1出现的次数

         1.确定状态参数和选择
         状态参数：字符串s的前i个字符 与字符串t的前j个字符为状态参数
         选择/决策： 不断选择i,j

         2.定义dp table的含义
         int[][] dp = new int[m+1][n+1];
         dp[m][n]表示 前m个字符的s的子序列中 前n个字符的t的出现个数


         3.初始化dp talbe
         当s是空串t也是空串的时候，也算包含一次
         当s不为空串t为空串时，也算包含一次
         当t不为空串s为空串时，不包含

         for(int i=0; i<=m; i++){
         dp[i][0] = 1;
         }

         4.推导状态转移公式
         由子问题推导原问题的解

         // i == j 有两种情况 选择当前和不选择当前
         if(ss[i-1] == tt[j-1]){
         dp[i][j] = dp[i-1][j] + dp[i][j];
         }else{
         dp[i][j] = dp[i-1][j];
         }
         */

        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        int m = ss.length;
        int n = tt.length;
        int[] dp = new int[n+1];
        dp[0] = 1;

        for (int i = 1; i <=m; i++) {
            for (int j = n; j >=1; j--) {
                if (ss[i - 1] == tt[j - 1]) {
                    dp[j] = dp[j - 1] + dp[j];
                } else {
                    dp[j] = dp[j];
                }
            }
        }

        return dp[n];

    }
}
